package com.lee.algorithm.sort;

/***
 * @description: 插入排序
 * @author : 青石路
 * @date: 2021/11/22 9:30
 */
public class InsertSort {

    public static void main(String[] args) {
        int[] arr = new int[]{1,0,4,3,2,9,7};
        insertSort(arr);
        SortUtil.print(arr);
    }

    /**
     * 从 i ~ n 中找到最小的元素
     * @param arr
     */
    public static void insertSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }

        // 0~0有序
        // 0~i-1已有序，处理 i~n
        for(int i=1; i<arr.length; i++) {

            // 将 arr[i]插入有序列表 arr[0...j]； 相邻（arr[j] 与 arr[j + 1]）做比较
            for (int j=i-1; j>=0 && arr[j]>arr[j+1]; j--) {
                SortUtil.swap(arr, j, j+1);
            }
        }
    }
}
